// 给定一个字符串s，一个字符串t
// 要求返回 s中涵盖t所有字符的最小子串，如果s中不存在涵盖t所有字符的子串，则返回空字符串''

// 思路，滑动窗口
function minWindow(s, t) {
    let charMap = new Map
    // 先把需要覆盖的字符映射到map中
    for (const char of t) {
        if (!charMap.has(char)) {
            charMap.set(char, 1)
        } else {
            charMap.set(char, charMap.get(char) + 1)
        }
    }
    let left = 0
    let right = 0
    let result = ''
    let needTypeCount = charMap.size
    while (right < s.length) {
        let cur = s[right]
        // 更新map中的映射值
        if (charMap.has(cur)) {
            charMap.set(cur, charMap.get(cur) - 1)
        }
        if (charMap.get(cur) === 0) {
            needTypeCount--
        }
        // 当覆盖完全之后，更新目标值
        while (needTypeCount === 0) {
            let str = s.substring(left, right + 1)
            if (!result || str.length < result.length) {
                result = str
            }
            let leftVal = s[left]
            if (charMap.has(leftVal)) {
                charMap.set(leftVal, charMap.get(leftVal) + 1)
                if (charMap.get(leftVal) === 1) {
                    needTypeCount++
                }
            }
            left++
        }
        right++
    }
    return result
}

let s = "ADOBECODEBANC", t = "ABC"
console.log(minWindow(s, t));